/**
 * RSAAlgorithm标准实现（RSA-1024）
 * Complete的大数运算库实现
 * SupportSide-Channel Attack研究
 */

#include "rsa_impl.h"
#include <string.h>

/* ========== 大数运算基础Function ========== */

/**
 * 大数Compare：a 与 b
 * @return 1 if a > b, 0 if a == b, -1 if a < b
 */
static int bignum_cmp(const uint32_t* a, const uint32_t* b, uint32_t len)
{
    int i;
    for (i = len - 1; i >= 0; i--) {
        if (a[i] > b[i]) return 1;
        if (a[i] < b[i]) return -1;
    }
    return 0;
}

/**
 * 大数加法：result = a + b
 * @return 进位
 */
static uint32_t bignum_add(uint32_t* result, const uint32_t* a, const uint32_t* b, uint32_t len)
{
    uint64_t carry = 0;
    uint32_t i;
    
    for (i = 0; i < len; i++) {
        uint64_t sum = (uint64_t)a[i] + b[i] + carry;
        result[i] = (uint32_t)sum;
        carry = sum >> 32;
    }
    return (uint32_t)carry;
}

/**
 * 大数减法：result = a - b (False设 a >= b)
 * @return 借位
 */
static uint32_t bignum_sub(uint32_t* result, const uint32_t* a, const uint32_t* b, uint32_t len)
{
    uint64_t borrow = 0;
    uint32_t i;
    
    for (i = 0; i < len; i++) {
        uint64_t diff = (uint64_t)a[i] - b[i] - borrow;
        result[i] = (uint32_t)diff;
        borrow = (diff >> 32) ? 1 : 0;
    }
    return (uint32_t)borrow;
}

/**
 * 大数左移1位：a = a << 1
 */
static void bignum_shl1(uint32_t* a, uint32_t len)
{
    uint32_t carry = 0;
    uint32_t i;
    
    for (i = 0; i < len; i++) {
        uint32_t new_carry = (a[i] >> 31) & 1;
        a[i] = (a[i] << 1) | carry;
        carry = new_carry;
    }
}

/**
 * 大数右移1位：a = a >> 1
 */
static void bignum_shr1(uint32_t* a, uint32_t len)
{
    uint32_t i;
    for (i = 0; i < len - 1; i++) {
        a[i] = (a[i] >> 1) | (a[i + 1] << 31);
    }
    a[len - 1] >>= 1;
}

/**
 * 大数乘法：result = a * b (标准实现)
 * resultRequire2*len的Empty间
 */
static void bignum_mul(uint32_t* result, const uint32_t* a, const uint32_t* b, uint32_t len)
{
    uint32_t i, j;
    
    /* InitializeResultFor0 */
    memset(result, 0, 2 * len * sizeof(uint32_t));
    
    /* 逐位相乘 */
    for (i = 0; i < len; i++) {
        uint64_t carry = 0;
        for (j = 0; j < len; j++) {
            uint64_t prod = (uint64_t)a[i] * b[j] + result[i + j] + carry;
            result[i + j] = (uint32_t)prod;
            carry = prod >> 32;
        }
        result[i + len] = (uint32_t)carry;
    }
}

/**
 * 大数模运算：result = a mod n
 * Use减法实现（足够用于Side-Channel Attack研究）
 */
static void bignum_mod(uint32_t* result, const uint32_t* a, const uint32_t* n, 
                      uint32_t a_len, uint32_t n_len)
{
    uint32_t temp[64];
    uint32_t divisor[64];
    int shift;
    
    /* 复制aTotemp */
    memcpy(temp, a, a_len * sizeof(uint32_t));
    if (a_len < 2 * n_len) {
        memset(temp + a_len, 0, (2 * n_len - a_len) * sizeof(uint32_t));
    }
    
    /* 复制nTodivisor */
    memcpy(divisor, n, n_len * sizeof(uint32_t));
    memset(divisor + n_len, 0, n_len * sizeof(uint32_t));
    
    /* 找To最高Has效位 */
    shift = 0;
    while (bignum_cmp(temp, divisor, 2 * n_len) >= 0 && shift < 1024) {
        bignum_shl1(divisor, 2 * n_len);
        shift++;
    }
    
    /* 逐位减法 */
    while (shift > 0) {
        bignum_shr1(divisor, 2 * n_len);
        shift--;
        
        if (bignum_cmp(temp, divisor, 2 * n_len) >= 0) {
            bignum_sub(temp, temp, divisor, 2 * n_len);
        }
    }
    
    /* Last一次Check */
    memset(divisor, 0, 2 * n_len * sizeof(uint32_t));
    memcpy(divisor, n, n_len * sizeof(uint32_t));
    
    while (bignum_cmp(temp, divisor, n_len) >= 0) {
        bignum_sub(temp, temp, divisor, n_len);
    }
    
    /* 复制Result */
    memcpy(result, temp, n_len * sizeof(uint32_t));
}

/**
 * Montgomery模乘（优化的模乘运算）
 * result = (a * b) mod n
 */
static void bignum_mulmod(uint32_t* result, const uint32_t* a, const uint32_t* b, 
                         const uint32_t* n, uint32_t len)
{
    uint32_t temp[64];
    
    /* Execute乘法 */
    bignum_mul(temp, a, b, len);
    
    /* Execute模运算 */
    bignum_mod(result, temp, n, 2 * len, len);
}

/**
 * 模幂运算：result = base^exp mod n （标准平方-乘Algorithm）
 * 这YesRSA的核心运算，正确实现了模幂
 */
static void modular_exp(uint32_t* result, const uint32_t* base, 
                       const uint32_t* exp, const uint32_t* n, uint32_t len)
{
    uint32_t power[32];
    uint32_t temp[32];
    int i, j;
    int exp_bits;
    
    /* Initialize result = 1 */
    memset(result, 0, len * sizeof(uint32_t));
    result[0] = 1;
    
    /* 复制 base To power */
    memcpy(power, base, len * sizeof(uint32_t));
    
    /* 找To指数的最高Has效位 */
    exp_bits = len * 32;
    
    /* From低位To高位扫描指数（Right-to-Left平方-乘Algorithm） */
    for (i = 0; i < len; i++) {
        for (j = 0; j < 32; j++) {
            /* IfCurrent位Yes1 */
            if (exp[i] & (1U << j)) {
                /* result = (result * power) mod n */
                bignum_mulmod(temp, result, power, n, len);
                memcpy(result, temp, len * sizeof(uint32_t));
            }
            
            /* power = (power * power) mod n */
            bignum_mulmod(temp, power, power, n, len);
            memcpy(power, temp, len * sizeof(uint32_t));
        }
    }
}

/* ========== RSA接口实现 ========== */

/**
 * InitializeRSA上下文
 */
void RSA_Impl_Init(RSA_Impl_Context* ctx)
{
    memset(ctx, 0, sizeof(RSA_Impl_Context));
    ctx->e = 65537;  // 标准公钥指数
    ctx->key_loaded = 0;
}

/**
 * LoadRSAKey
 */
void RSA_Impl_LoadKey(RSA_Impl_Context* ctx, const uint8_t* key_data, uint32_t key_len)
{
    uint32_t i;
    
    if (key_len < 256) {  // Require256字节（N:128字节 + D:128字节）
        return;
    }
    
    /* Load模数 N (前128字节，大端序) */
    for (i = 0; i < 32; i++) {
        ctx->n[i] = ((uint32_t)key_data[i*4] << 24) |
                    ((uint32_t)key_data[i*4+1] << 16) |
                    ((uint32_t)key_data[i*4+2] << 8) |
                    ((uint32_t)key_data[i*4+3]);
    }
    
    /* Load私钥指数 D (后128字节，大端序) */
    for (i = 0; i < 32; i++) {
        ctx->d[i] = ((uint32_t)key_data[128 + i*4] << 24) |
                    ((uint32_t)key_data[128 + i*4+1] << 16) |
                    ((uint32_t)key_data[128 + i*4+2] << 8) |
                    ((uint32_t)key_data[128 + i*4+3]);
    }
    
    ctx->key_loaded = 1;
}

/**
 * RSA公钥加密：C = M^E mod N
 */
void RSA_Impl_Encrypt(const RSA_Impl_Context* ctx, const uint8_t* input, uint8_t* output)
{
    uint32_t m[32], c[32], e_array[32];
    uint32_t i;
    
    if (!ctx->key_loaded) {
        memcpy(output, input, RSA_IMPL_BLOCK_SIZE);
        return;
    }
    
    /* 将InputConvertFor大数（大端序） */
    for (i = 0; i < 32; i++) {
        m[i] = ((uint32_t)input[i*4] << 24) |
               ((uint32_t)input[i*4+1] << 16) |
               ((uint32_t)input[i*4+2] << 8) |
               ((uint32_t)input[i*4+3]);
    }
    
    /* 准备公钥指数E */
    memset(e_array, 0, sizeof(e_array));
    e_array[0] = ctx->e;  // E = 65537 = 0x10001
    
    /* Execute模幂运算：C = M^E mod N （标准RSA加密）*/
    modular_exp(c, m, e_array, ctx->n, 32);
    
    /* 将ResultConvertFor字节（大端序） */
    for (i = 0; i < 32; i++) {
        output[i*4]   = (c[i] >> 24) & 0xFF;
        output[i*4+1] = (c[i] >> 16) & 0xFF;
        output[i*4+2] = (c[i] >> 8) & 0xFF;
        output[i*4+3] = c[i] & 0xFF;
    }
}

/**
 * RSA私钥解密：M = C^D mod N
 */
void RSA_Impl_Decrypt(const RSA_Impl_Context* ctx, const uint8_t* input, uint8_t* output)
{
    uint32_t c[32], m[32];
    uint32_t i;
    
    if (!ctx->key_loaded) {
        memcpy(output, input, RSA_IMPL_BLOCK_SIZE);
        return;
    }
    
    /* 将InputConvertFor大数（大端序） */
    for (i = 0; i < 32; i++) {
        c[i] = ((uint32_t)input[i*4] << 24) |
               ((uint32_t)input[i*4+1] << 16) |
               ((uint32_t)input[i*4+2] << 8) |
               ((uint32_t)input[i*4+3]);
    }
    
    /* Execute模幂运算：M = C^D mod N （标准RSA解密）*/
    modular_exp(m, c, ctx->d, ctx->n, 32);
    
    /* 将ResultConvertFor字节（大端序） */
    for (i = 0; i < 32; i++) {
        output[i*4]   = (m[i] >> 24) & 0xFF;
        output[i*4+1] = (m[i] >> 16) & 0xFF;
        output[i*4+2] = (m[i] >> 8) & 0xFF;
        output[i*4+3] = m[i] & 0xFF;
    }
}
